Given a sorted array a. Find the longest arithmetic progression.
Ex. 1 2 3 4 6 8 10 11 12 13 14 16 18.
The longest arithmetic progression is 2 4 6 8 10 12 14 16 18.
Sol: It’s a typical dynamic programming problem. We define 2-dimension state variable d(i,j) to denote the largest length of arithmetic progression which start with a[i], a[j]. So we initialize d(i,j) to 2. The logic here is straightforward: we scan a[j] from end to start and see the difference between a[j]-a[i] and a[k]-a[j] (i<j<k). If a[j]-a[i]>a[k]-a[j], we try larger one (k++); if a[j]-a[i]<a[k]-a[j] , that means we can’t extend arithmetic progression from a[i] a[j] any more. If a[j]-a[i]=a[k]-a[j], we update d[i][j] and max length.
01
#define MAXN 100;
02
int d[MAXN][MAXN];
03
int longestAP(int a[], int n){
04
   int maxlen=2;
05
   for(int j=n-2;j>=0;j--){
06
       int i=j-1,k=j+1;
07
       while(i>=0&&k<n){
08
          if(a[j]-a[i] > a[k]-a[j])
09
            k++;
10
          else if(a[j]=a[i] < a[k]-a[j]){
11
            d[i][j]=2;
12
            i--;
13
          }
14
          else {
15
            d[i][j]=d[j][k]+1;
16
            maxlen=maxlen<d[i][j]?d[i][j]:maxlen;
17
            i--;
18
            k++;
19
          }
20
        }
21
       while(i>=0){
22
           d[i][j]=2;
23
           i--;
24
       }
25
   }
26
   return maxlen;
27
}

